package codingforgreat.class06;

import com.sun.xml.internal.ws.handler.HandlerException;
//lc 421
public class Class02_MaximumXorOfTwoNumbersInAnArray {

    public class Node{
        public Node[] nexts = new Node[2];
    }

    public class TireTree{
        public  Node head = new Node();
        public void add(int num){
            Node  node = head;
            for (int i = 31; i >= 0 ; i--) {
                int path =  (num >> i) & 1;
                if ( null == node.nexts[path]) {
                    node.nexts[path] = new Node();
                }
                node = node.nexts[path];
            }
        }

        public int findMaximumXOR(int num){
            Node node = head;
            int ans = 0;
            for (int i = 31; i >= 0 ; i--) {
                int path = (num >> i) & 1;
                int best = i == 31 ? path : path ^ 1;
                best = node.nexts[best] == null ? best ^ 1 : best;
                ans |= (path ^ best) << i;
                node = node.nexts[best];
            }
            return  ans;
        }
    }
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length < 2){
            return 0;
        }
        TireTree tireTree = new TireTree();
        tireTree.add(nums[0]);
        int max = Integer.MIN_VALUE;;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, tireTree.findMaximumXOR(nums[i]));
            tireTree.add(nums[i]);
        }
        return max;
    }
}
